/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
//作者:AKPower
//算法:
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const ll maxn = 310;
const ll INF = 0x3f3f3f3f;
ll a[maxn][maxn];
ll dis[maxn];
ll path[maxn];
ll n;
bool vis[maxn];
struct node
{
    ll y, val;
    node(ll x1, ll x2)
    {
        y = x1;
        val = x2;
    };
};
vector<node> p[maxn];
vector<ll> Path;
int main()
{
    IOS;
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            if (i != j && a[i][j] == 1)
            {
                p[i].push_back(node(j, -1));
            }
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        path[i] = -1;
        dis[i] = INF;
    }
    for (ll i = 0; i < p[1].size(); i++)
    {
        dis[p[1][i].y] = p[1][i].val;
        path[p[1][i].y] = 1;
    }
    vis[1] = true;
    for (ll i = 1; i < n; i++)
    {
        ll index = -1, minn = INF;
        for (ll j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] < minn)
            {
                minn = dis[j];
                index = j;
            }
        }
        if (index == -1)
        {
            // cout << "hello" << endl;
            break;
        }
        vis[index] = true;
        for (ll j = 0; j < p[index].size(); j++)
        {
            ll ty = p[index][j].y;
            ll val = p[index][j].val;
            if (!vis[ty] && dis[ty] > dis[index] + val)
            {
                dis[ty] = dis[index] + val;
                path[ty] = index;
            }
        }
    }
    if (dis[n] == INF)
    {
        cout << -1 << endl;
    }
    else
    {
        // Path.push_back(n);
        for (ll id = n; id != -1; id = path[id])
        {
            Path.push_back(id);
            // cout << id << " ";
        }
        // cout << endl;
        reverse(Path.begin(), Path.end());
        ll len = Path.size();
        ll las = 1;
        ll ans = 0;
        for (ll i = 1; i < len; i++)
        {
            ll id = Path[i];
            // cout << id << " ";
            for (ll j = 1; j < id; j++)
            {
                if (a[las][j] == 1)
                    ans++;
            }
            las = id;
        }
        // cout << endl;
        cout << ans << endl;
    }
    getchar();
    getchar();
    return 0;
}
